#pragma once
#include "IndexSet.hpp"
#include "../Math/Math.hpp"
#include "Log.hpp"

// It is a kind of indexed set.
// It will return an object based on an index.
// What's special is that it will cache some objects based on Least-Recent-Access.
// When an object is added, and cache is full, one object will deleted.
// When some objects need to be deleted, the Least-Recent-Access object will be deleted.

namespace zzz{
template<typename T, typename IDX=zuint>
class CacheSet : public IndexSet<T, IDX>
{
public:
  CacheSet(int cache_size=10):cache_size_(cache_size), INVALID_INDEX(MAX_UINT){}
  virtual ~CacheSet(){Clear();}

  // Set all data size and cache size
  // Will call Reset()
  void SetSize(zuint cache_size)
  {
    ZCHECK_GT(cache_size, 0);
    cache_size_=cache_size;
    Reset();
  }

  void Add(const IDX &i, T x)
  {
    // Object is not in cache, replace the tail(least recent get one).
    if (data_[tail_]) {
      delete data_[tail_];
      idx_to_obj_.erase(idx_[tail_]);
    }
    data_[tail_]=x;
    idx_[tail_]=i;
    idx_to_obj_[i]=tail_;
    MoveFront(tail_);
  }

  // Get data, user only need this
  T Get(const IDX &i)
  {
    if (!CheckIndex(i)) {
      ZLOG(ZERROR)<<"CheckIndex() failed!\n";
      return NULL;
    }
    
    map<IDX, zuint>::iterator mi = idx_to_obj_.find(i);
    if (mi != idx_to_obj_.end()) {
      // Object is in cache, move item to front and return directly.
      MoveFront(mi->second);
      return data_[mi->second];
    }
    // Object is not in cache, return NULL.
    return NULL;
  }

  // User can overload this function to check index, for security reasons.
  virtual bool CheckIndex(const IDX &i){return true;}

  //clear all
  void Clear()
  {
    for(zuint i=0; i<data_.size(); i++) {
      if(data_[i]!=NULL) {
        delete data_[i];
        data_[i]=NULL;
      }
    }
    data_.clear();
    idx_to_obj_.clear();
    prev_.clear();
    next_.clear();
  }
protected:
  // Reset and load cache.
  // Should be called before start.
  void Reset()
  {
    Clear();
    idx_to_obj_.clear();
    head_=0;
    tail_=cache_size_-1;
    data_.assign(cache_size_, 0);
    idx_.resize(cache_size_);
    prev_.assign(cache_size_, 0);
    next_.assign(cache_size_, 0);
    for (zuint i=0; i<cache_size_; i++) {
      if (i!=0) prev_[i]=i-1;
      else prev_[i]=INVALID_INDEX;
      if (i!=cache_size_-1) next_[i]=i+1;
      else next_[i]=INVALID_INDEX;
    }
  }

  //move to front
  void MoveFront(zuint i)
  {
    //head
    if (i==head_) 
      return;
    else if (i==tail_) {
      //tail to head, prev of tail is tail
      prev_[head_]=i;
      next_[i]=head_;
      head_=i;
      tail_=prev_[i];
      prev_[i]=INVALID_INDEX;
      next_[tail_]=INVALID_INDEX;
      return;
    } else {
      //middle
      next_[prev_[i]]=next_[i];
      prev_[next_[i]]=prev_[i];
      next_[i]=head_;
      prev_[i]=INVALID_INDEX;
      prev_[head_]=i;
      head_=i;
    }
  }

  zuint cache_size_;
  map<IDX,zuint> idx_to_obj_;

  zuint head_, tail_;
  vector<T> data_;
  vector<IDX> idx_;
  vector<zuint> prev_, next_;

  const zuint INVALID_INDEX;
};
}